
//3342.到达最后以一个房间的最少时间II
class Solution {
public:
    int minTimeToReach(vector<vector<int>>& moveTime) {
        //因为地窖是一个网格状排布,所以基本上每个房间与房间之间都有联系,所以使用堆进行处理效率更高
        //使用Dijkstra 算法

        //对于房间开始并可达的时间可以记作图中的边权,如果当前时间更大,这边权是1,否则边权就是moveTime[a][b]+1
        int n = moveTime.size() , m = moveTime[0].size();
        vector<vector<int>> dis(n,vector<int>(m,INT_MAX));   //记录到达的位置所需要的最短时间
        vector<vector<int>> vist(n,vector<int>(m));          //记录已经去过的位置
        priority_queue<tuple<int,int,int,int>,vector<tuple<int,int,int,int>>,greater<tuple<int,int,int,int>>> pq;               //记录每个位置到达需要的时间,以及坐标

        int dx[] = {0,0,-1,1};
        int dy[] = {1,-1,0,0};

        pq.push({0,0,0,1});
        vist[0][0] = 1;
        while(!pq.empty())
        {
            auto [clock,x,y,step] = pq.top();
            pq.pop();
            if(dis[x][y] <= clock) continue;
            dis[x][y] = clock;
            int next = step%2==0?2:1;           //计算当前步数需要花费的秒数
            for(int k = 0; k < 4; k++)
            {
                int a = x + dx[k],b = y + dy[k];
                if(a >= 0 && a < n && b >= 0 && b < m && !vist[a][b] )
                {
                    vist[a][b] = 1;
                    if(clock >= moveTime[a][b] && clock + next < dis[a][b])   pq.push({clock+ next,a,b,step+1});
                    else if(clock < moveTime[a][b] && moveTime[a][b] + next < dis[a][b]) pq.push({moveTime[a][b]+next ,a,b,step+1});
                }
            }
        }
        return dis[n-1][m-1];
    }
};